1. Field of the Invention
The present invention relates in general to data processing, and more particularly, to an apparatus and method of providing high speed table generation for block encryption.
2. Description of the Related Art
Encryption techniques are generally implemented in the transmission of digital information to conceal information from unintended recipients and for authenticating messages to assure the recipient of sender identity. Encryption is also used for digital signatures, to authenticate and assure the recipient that any third party could not have created the signature. As in physical security systems, encryption provides assurance of integrity including prevention of interference in the information-conveying process or failing that, detecting interference. Interference in this context includes eavesdropping, modifying, introducing misinformation, disavowing messages and falsely claiming receipt of messages.
Almost all cryptosystems involve transformation of information based on one or more keys, at least one of which must be kept secret to protect against adversaries. Block substitution is an encryption process used to encrypt a clear text message which is in the form of a sequence of binary numbers. Typically, a block substitution system consists of alternating steps of encrypting conveniently-sized sub-blocks in individual substitution boxes (S-boxes) and permuting the partly encrypted data. Substitute blocks constitute the encrypted message or cipher text, each substitute block representing a non-ambiguous one-to-one transformation of a clear text block. After dividing the block of clear text into sub-blocks and encrypting the sub-blocks, the encrypted sub-blocks are typically reassembled into a block and the bits in the full block are permuted. The resulting block is again subdivided into sub-blocks for another round of encryption. As shown in FIG. 1, this process of substitution-permutation-substitution is repeated a number of times.
In many systems like DES and its variations, these individual S-boxes are fixed. In such systems, the tables might as well be publicly known, as they will be eventually revealed with the passage of time. In DES-like systems, the key interacts with the data. The S-boxes have the vital role of acting as a barrier to prevent the cryptanalyst from using matching clear text/cipher text pairs to find bits of the key. The S-box tables in such systems have to be designed with great care and thoroughly tested before selection as permanent parts of the algorithm.
An alternate approach involves the use of one-time tables in the S-boxes. These tables are selected by the key, kept secret or at least not made public, and changed as frequently as the key is changed. This approach presents several challenges. First of all, it must be possible to find a selection of S-box tables that are known to be of good quality without testing. Secondly, the supply of such tables must be very large so that duplication is unlikely. Related to the first requirement is the fact that the cryptographic community demands that cryptographic strength be assessed not only by empirical testing but also by underlying mathematical theory. The so-called spaghetti algorithms that are very complex but without any recognizable mathematical structure are viewed with skepticism. Despite having passed standard tests with flying colors there is the lingering doubt that there may be exploitable weaknesses lurking in the murky complexity.
U.S. Pat. Nos. 5,038,376, 5,214,704, 5,317,639 and 5,647,001 disclose cryptographic block substitution systems in which dynamic substitution devices (DSD) are used as substitution boxes (S-boxes). In these substitution systems, orthomorphic mapping is applied. In particular, U.S. Pat. Nos. 5,038,376, 5,214,704, 5,317,639 and 5,647,001 disclose methods for generating orthomorphic mapping tables of good quality, in terms of cryptographic strength, and in ample quantities. However, the method covered by the first three patents were restrictive in the sense that not all possible orthomorphisms could be generated. Some of the methods permit more rapid generation than others which is important for some but not all applications. U.S. Pat. No. 5,647,001 includes the so-called bar sinister method. It can be shown mathematically that this method can generate all possible orthomorphisms. Further, using this method, we obtain the best quality in terms of measures of cryptographic strength. However, there is one drawback to the bar sinister method, namely, that it is relatively slow in generating tables. It may take several seconds to generate a table for 8-bit numbers, which is too long for some applications.
Accordingly, there is a need in the technology for an apparatus and method for providing high speed table generation for block encryption. There is also a need in the technology for an apparatus and method for generating mappings in general, and for generating orthomorphisms for block encryption, which have high cryptographic strength and which can be generated quickly and efficiently.